<!DOCTYPE html>
<html>
<head>
    <meta charset="utf-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge,chrome=1">
    <title>寻径算法</title>
    <meta name="description" content="">
    <meta name="keywords" content="">
    <link href="" rel="stylesheet">
    <style>
        .button{
            width: 531px;
            margin: 10px auto;
        }
        table{
            border-collapse: collapse;
            width: 531px;
            margin: 0 auto;
        }
        td{
            width: 50px;
            height: 50px;
            border:1px solid orange;
        }
        td.start{
            background: url(http://1814.img.pp.sohu.com.cn/images/blog/2010/1/28/13/13/127242e5097g215.jpg) no-repeat center center;
            background-size: 100% 100%;
        }
        td.end{
            background: url(http://demo.deanhan.cn/findpath/fish.png) no-repeat center center;
            background-size: 100% 100%;
        }
        td.current{
            background: skyblue;
        }
        td.path{
            background: url(http://cdn-img.easyicon.net/png/5308/530838.gif) no-repeat center center;
            background-size: 100% 100%;
        }
        td.block{
            background: url(http://ico.ooopic.com/iconset01/open-icon-library-others-icons/gif/119576.gif) no-repeat center center;
            background-size: 80% 80%;
        }
    </style>
</head>
<body>
<div class="button">
    <button onclick="javascript:console.time('t');finder();console.timeEnd('t');">去吃鱼啦</button>
</div>
<script type="text/javascript">
    /**
         其实就我理解，这个算法的主要实现思路是这样的：
         首先遍历了整个map（生成map的过程就不说了，说的直白点就是一个数组），
         然后处理每个点的上下左右四个位置，如果有阻碍物（可以通过为0，不能通过为1）或者已经添加到steps数组就不做处理，
         剩下的添加到steps数组中，该点的值就是上一个点的位置，
         当然如果四个点中有一个已经是最终的点了
         那整个遍历结束 这样我们就得到了路径数组，
         现在我们需要做的就是根据我们的得到的steps数组获取最终路径，
         过程是这样的，
         我们将将steps数组按照从后到前的顺序依次寻找父节点，
         直到到达起始点，
         这样子得出的一条路径就是最终得路径了。
     */
    var rows = 10,cols =10;
    var map = multiArray(rows,cols),elems = multiArray(rows,cols);
    var start = [0,0];
    var end = [6,6];
    var table = document.createElement("table");
    for(var i=0,l=map.length;i<l;i++){
        var tr = document.createElement("tr");
        for(var j=0,ll=map[i].length;j<ll;j++){
            var td = document.createElement("td");
            if(i==start[1]&&j==start[0]){
                td.className = "start";
            }
            if(i==end[1]&&j==end[0]){
                td.className = "end";
            }
            elems[j][i] = tr.appendChild(td);
            (function(i,j){
                td.onclick = function(){
                    clearPath();
                    if(elems[j][i].className=="block"){
                        elems[j][i].className = "";
                        map[j][i] = 0;
                    }else if(!elems[j][i].className){
                        elems[j][i].className = 'block';
                        map[j][i] = 1;
                    }
                }
            })(i,j);
        }
        table.appendChild(tr);
    }
    document.body.appendChild(table);
    function finder(){
        clearPath();
        var result = [];
        var finded =false;
        var steps = multiArray(rows,cols);
        (function(list){
            var next_list = [];
            var next = function(from,to){
                var x = to[0],y = to[1];
                if(typeof steps[x]!= 'undefined' && typeof steps[x][y]!='undefined' && !map[x][y] && !finded){
                    if(x==end[0] && y==end[1]){
                        finded = true;
                        steps[x][y] = from;
                    }else if(!steps[x][y]){
                        next_list.push(to);
                        steps[x][y] = from;
                    }
                }
            }
            for(var i=0,l=list.length;i<l;i++){
                var current = list[i];
                var x = current[0],y = current[1];
                (x-1>=0) && next(current,[x-1,y]);
                (x+1<cols) && next(current,[x+1,y]);
                (y-1>=0) && next(current,[x,y-1]);
                (y+1<rows) && next(current,[x,y+1]);
            }
            if(!finded && next_list.length){
                arguments.callee(next_list);
            }
        })([start]);
        if(finded){
            // TODO打印输出
            console.log("结果类   0     1     2     3     4     5     6     7     8     9     10")
            for(var i in steps){
                console.log("结果"+i,JSON.stringify(steps[i]));
            }
            var current = end;
            while(current[0]!=start[0]||current[1]!=start[1]){
                result.unshift(current);
                console.log("current",current)
                current = steps[current[0]][current[1]];
            }
        }
        console.log("result",result)
        for(var i=0,l=result.length;i<l;i++){
            if(result[i][0]==end[0]&&result[i][1]==end[1]) continue;
            elems[result[i][0]][result[i][1]].className = 'path';
        }
    }
    function multiArray(rows,cols){
        var a = new Array(rows);
        for(var i=0,l=a.length;i<l;i++){
            a[i] = new Array(cols);
            for(var j=0;j<cols;j++){
                a[i][j] = 0;
            }
        }
        return a;
    }
    function clearPath(){
        for(var i=0,l=map.length;i<l;i++){
            for(var j=0,ll=map[i].length;j<ll;j++){
                if(elems[j][i].className=="path"){
                    elems[j][i].className = "";
                }
            }
        }
    }
</script>
</body>
</html>